package com.localking.algorithm.leetcode.array

/**
 * Given an array, rotate the array to the right by k steps, where k is non-negative.
 *
 * Example 1:
 * Input: [1, 2, 3, 4, 5, 6, 7] and k = 3
 * Output: [5, 6, 7, 1, 2, 3, 4]
 * Explanation:
 * rotate 1 steps to the right: [7, 1, 2, 3, 4, 5, 6]
 * rotate 2 steps to the right: [6, 7, 1, 2, 3, 4, 5]
 * rotate 3 steps to the right: [5, 6, 7, 1, 2, 3, 4]
 *
 * Example 2:
 * Input: [-1, -100, 3, 99] and k = 2
 * Output: [3, 99, -1, -100]
 * Explanation:
 * rotate 1 steps to the right: [99, -1, -100, 3]
 * rotate 2 steps to the right: [3, 99, -1, -100]
 *
 * Note:
 * * Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
 * * Could you do it in place with O(1) extra space?
 *
 * @author jinbo
 */
object RotateArray {

  def main(args: Array[String]): Unit = {
    val nums = Array(1, 2, 3, 4, 5, 6, 7)
    rotate(nums, 3)
  }
  def rotate(nums: Array[Int], k: Int): Unit = {
    val length = nums.length
    val splitIndex = length - k % length - 1
    reverseArray(nums, 0, splitIndex)
    reverseArray(nums, splitIndex + 1, length - 1)
    reverseArray(nums, 0, length - 1)
    println(nums.mkString("[", ", ", "]"))
  }

  def reverseArray(nums: Array[Int], startIndex: Int, endIndex: Int): Unit = {
    var currentStartIndex = startIndex
    var currentEndIndex = endIndex
    while (currentStartIndex < currentEndIndex) {
      val temp = nums(currentEndIndex)
      nums(currentEndIndex) = nums(currentStartIndex)
      nums(currentStartIndex) = temp
      currentStartIndex += 1
      currentEndIndex -= 1
    }
  }
}
